/***************************************************************************
 *   Copyright (C) 2007 by Warren,,,   *
 *   warren@warren-dev   *
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 *   This program is distributed in the hope that it will be useful,       *
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
 *   GNU General Public License for more details.                          *
 *                                                                         *
 *   You should have received a copy of the GNU General Public License     *
 *   along with this program; if not, write to the                         *
 *   Free Software Foundation, Inc.,                                       *
 *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
 ***************************************************************************/
#ifndef GSSORT_H
#define GSSORT_H

#include <gsCore/gsCore.h>

/**
	@author Warren,,, <warren@warren-dev>
	
	gsSort contains static methods for sorting arrays of objects. Please be aware that the object you submit to gsSort's methods must either be 
	primitive object types or have overloaded comparison operators in order for each algorithm to compare object groups
*/
template< class T >
class gsSort
{
public:
    	///
	///	Constructor(s)
	///
	
	
	/**
	 *        Default Constructor
	 */
	gsSort();
	
	///
	///	Miscellaneous Methods
	///
	
	/**
	 * 	Simple sorting algorithm that works by swapping elements in multiple passes. O(n^2) operations required
	 * @param objectBuffer A pointer to the buffer containing the objects
	 * @param objectCount The number of objects in the buffer
	 */
	static inline void bubbleSort( T* objectBuffer, const unsigned int objectCount )
	{
		gsBool complete = false;
		while( !complete )
		{
			complete = true;
			for( gsUInt i = 0; i < (objectCount-1); i++ )
			{
				if( *(objectBuffer + i) > *(objectBuffer + i + 1) )
				{
					swap( (objectBuffer + i), (objectBuffer + i + 1) );
					complete = false;
				} 
			}
		}
	}
	
	/**
	 * 	Simple algorithms that scans the buffer for the smallest element, O(n) operations required
	 * @param objectBuffer A pointer to the buffer containing the objects
	 * @param objectCount The number of objects in the buffer
	 */
	static inline void selectionSort( T* objectBuffer, const unsigned int objectCount )
	{
		gsUInt offset = 0;
		while( offset < objectCount )
		{
			T* mark = ( objectBuffer + offset );
			for( gsUInt i = offset; i < objectCount; i++ )
			{
				if( *(objectBuffer + i) < *mark )
				{
					mark = (objectBuffer + i);
				} 
			}
			if( mark != (objectBuffer + offset) )
			{
				swap( mark, ( objectBuffer + offset ) );
			}
			offset++;
		}
	}
	
	/**
	 * 	Simple algorithm that is particularly efficient for smaller buffers or buffers which require few inversions
	 * @param objectBuffer A pointer to the buffer containing the objects
	 * @param objectCount The number of objects in the buffer
	 */
	static inline void insertionSort( T* objectBuffer, const unsigned int objectCount )
	{
	}
	
	
	/**
	 * 	Improved version of insertion sort which uses variable gap sizes to sort the buffer more quickly
	 * @param objectBuffer A pointer to the buffer containing the objects
	 * @param objectCount The number of objects in the buffer
	 */
	static inline void shellSort( T* objectBuffer, const unsigned int objectCount )
	{
	}
	
	/**
	 * 	Divide and conquer sorting algorithm with O( n log(n) ) performance
	 * @param objectBuffer A pointer to the buffer containing the objects
	 * @param objectCount The number of objects in the buffer
	 */
	static inline void mergeSort( T* objectBuffer, const unsigned int objectCount )
	{
	}
	
	/**
	 * 	O(n log(n)) sorting algorithm that uses a heap/binary tree restructuring system to determine the largest element
	 * @param objectBuffer A pointer to the buffer containing the objects
	 * @param objectCount The number of objects in the buffer
	 */
	static inline void heapSort( T* objectBuffer, const unsigned int objectCount )
	{
	}
	
	/**
	 * 	Simple divide and conquer sorting algorithm, variable efficiency depending on choice of pivot, generally O( n log(n) )
	 * @param objectBuffer A pointer to the buffer containing the objects
	 * @param objectCount The number of objects in the buffer
	 */
	static inline void quickSort( T* objectBuffer, const unsigned int objectCount )
	{
	}
	
	/**
	 * 	Simple sorting algorithm that partitions the buffer and then uses an external sorting algorithm ( insertion sort ) to sort the 'buckets'
	 * @param objectBuffer A pointer to the buffer containing the objects
	 * @param objectCount The number of objects in the buffer
	 */
	static inline void bucketSort( T* objectBuffer, const unsigned int objectCount )
	{
	}
	
	///
	///	Destructor(s)
	///
	
    	/**
    	 *    Default destructor
    	 */
    	~gsSort();

protected:
	
	/**
	 * 	Swap the positions of two elements
	 * @param alpha The first element
	 * @param beta The second element
	 */
	inline void swap( T* alpha, T* beta )
	{
		T temp = *alpha;
		*alpha = *beta;
		*beta = temp;
	}
	
};

#endif
